package leetcode.code0375;

import java.util.TreeSet;

public class Solution3751 {

	private static TreeSet<Integer> range;

	static {
		range = new TreeSet<>();
		long num = 1;
		while (num < Integer.MAX_VALUE) {
			range.add((int) num);
			num <<= 1;
		}
	}

	public int getMoneyAmount(int n) {
		int l = range.ceiling(n);
		return this.f(1, n);
	}

	private int f(int l, int r) {
		if (l >= r) {
			return 0;
		}
		int ans = Integer.MAX_VALUE;
		for (int i = l; i <= r; i++) {
			int left = this.f(l, i - 1);
			int right = this.f(i + 1, r);
			int cur = Math.max(left, right) + i;
			ans = Math.min(ans, cur);
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution3751 so = new Solution3751();
		int ans = so.getMoneyAmount(22);
		System.out.println(ans);
	}
}
